package leetcode.doublepointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//986. 区间列表的交集
public class IntervalIntersection {
    public static void main(String[] args) {
        int[][] data1 = {{0, 2}, {5, 10}, {13, 23}};
        int[][] data2 = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
        int[][] ints = intervalIntersection(data1, data2);
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[0].length; j++) {
                System.out.print("\t " + ints[i][j]);
            }
            System.out.println();
        }


    }

    /**
     * 思路：
     * 双指针指向每个区间的头，取A中每一个区间的头和B中每一个区间的头的最大值(left)，
     * 取A中每一个区间的尾和B中每一个区间的尾的最小值(right)，如果 left<=right，说明有交集，否则说明没有交集
     * 指针移动的时机：
     * 1.较长的子区间还有可能和别人重叠，它的指针暂时不动。
     * 2.求完一个交集区间后，较早结束的子区间，不可能再和别的子区间重叠（因为是有序的，它不可能与后面的有重叠），
     * 它的指针要移动。
     * <p>
     * 总结：
     * 一个子区间可能足够长，以至于和多个子区间重叠。
     * 因此在移动指针时，要做判断。
     *
     * @param firstList
     * @param secondList
     * @return
     */
    public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res = new ArrayList<>();
        int p = 0;
        int q = 0;
        while (p < firstList.length && q < secondList.length) {
            int left = Math.max(firstList[p][0], secondList[q][0]);
            int right = Math.min(firstList[p][1], secondList[q][1]);
            if (left <= right) {
                //说明有交集
                res.add(new int[]{left, right});
            }
            if (firstList[p][1] < secondList[q][1]) {
                //如果第一个数组的尾比第二个数组的尾小的话
                p++;
            } else {
                q++;
            }
        }
        return res.toArray(new int[0][0]);
    }
}
